﻿#pragma once
#include "Index.h"
#include "LinkListFindKthFromTail.h"

class ListKthTail
{
public:
	static ListNode* findKthToTail(ListNode* head, int k)
	{
		LinkListFindKthToTail::Solution solution;
		return solution.findKthToTail(head,k);
	}

	/**
	 * 给定一个链表，删除链表的倒数第k个节点并返回链表的头指针
	 * 例如，
	 * 给出的链表为: 1→2→3→4→5,k=2.
	 * 删除了链表的倒数第k个节点之后,链表变为 1→2→3→5.
	 *
	 * 使用头插法临时给链表添加一个表头，找到头插法后的倒数第k+1个节点，这个节点为要删除的目标节点的前一个节点.
	 */
	static ListNode* removeKthFromEnd(ListNode* head, int k)
	{
		if (!head || k <= 0)
			return head;
		ListNode* app_head = new ListNode();
		app_head->next = head;

		ListNode* pre = findKthToTail(app_head, k + 1);
		if (!pre)
			return head;

		ListNode* remove = pre->next;
		pre->next = remove ? remove->next : nullptr;

		return app_head->next;
	}
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(ListKthTailNodeTest, removeKthFromEnd)
{
	ListNode* head = ListUtil::createListFromValues({ 1,2,3,4,5,6,7,8 });
	const std::size_t list_size = ListUtil::getListLength(head);

	ListKthTail solution;
	//删除倒数最前面
	ListNode* removed_head = solution.removeKthFromEnd(ListUtil::createListFromClone(head), 1);
	EXPECT_TRUE(ListUtil::isEqual(removed_head, "1,2,3,4,5,6,7"));

	//删除倒数最后面
	removed_head = solution.removeKthFromEnd(ListUtil::createListFromClone(head), list_size);
	EXPECT_TRUE(ListUtil::isEqual(removed_head, "2,3,4,5,6,7,8"));

	//删除倒数中间的数
	removed_head = solution.removeKthFromEnd(ListUtil::createListFromClone(head), list_size / 2);
	EXPECT_TRUE(ListUtil::isEqual(removed_head, "1,2,3,4,6,7,8"));

	//不合法的输入则不进行删除
	removed_head = solution.removeKthFromEnd(ListUtil::createListFromClone(head), list_size + 1);
	EXPECT_TRUE(ListUtil::isEqual(removed_head, "1,2,3,4,5,6,7,8"));
	removed_head = solution.removeKthFromEnd(ListUtil::createListFromClone(head), -1);
	EXPECT_TRUE(ListUtil::isEqual(removed_head, "1,2,3,4,5,6,7,8"));
}
#endif